package NowCoder.Mathematics;
import java.util.*;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/95e35e7f6ad34821bc2958e37c08918b
 * 来源：牛客网
 *
 * 发邮件
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
 * NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？
 * 即没有人收到属于自己的邮件。
 *
 * 输入描述:
 * 输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。
 *
 * 输出描述:
 * 对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。
 *
 * 示例1
 * 输入
 * 2<br/>3
 * 输出
 * 1<br/>2
 */

public class 发邮件_编程_1_7_13 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            long n = sc.nextLong();
            System.out.println(allWrongNumber(n));
        }
    }

    //错排问题，推导如下,
    //若前n-1个数已经满足错排，现考虑第n个数：
    //（1）第n个数可以和前n-1个中任意一个数互换，结果仍然是错排，所以有(n-1)*D(n-1)种；
    //（2）第n个数可以放到前n-1任意一个位置，但是原来位置的数不能放到最后(PS:这里因为前一种情况已经计算到过)，
    //     则其只可以能放在其他n-2个位置，并且保证这n-2的位置是错排，所以有(n-1)*D(n-2)
    //综上，一共有 D(n) =（n-1）*(D(n-1)+D(n-2))
    public static long allWrongNumber(long n){
        if(n < 2){
            return 0;
        }

        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        return (n - 1) * (allWrongNumber(n - 1) + allWrongNumber(n - 2));
    }
}
